import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
 * 请你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。

 * 思路
 * 1.枚举前两个数，最后一个可以用二分（排序后）
 * 2.去重策略：对于每一位数，取值只取一次（需要排序）
 * @since 2023-08-27 17:16
 */
public class _015三数之和 {
    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println( threeSum(nums));
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int l, r, mid;
        int target;
        //排序
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            //去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < nums.length; j++){
                //去重
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                //二分查找
                l = j + 1;
                r = nums.length - 1;
                target = -(nums[i] + nums[j]);
                if(target < 0) break;   //不可能情况
                while(l <= r){
                    mid = l + ((r - l) >> 1);
                    if(nums[mid] == target){    //找到一种情况
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[mid]);
                        res.add(list);
                        break;
                    }else if(nums[mid] > target){
                        r = mid - 1;
                    }else{
                        l = mid + 1;
                    }
                }
            }
        }
        return res;
    }
}
